// 邻接表存储有向图

#include <stdio.h>
#include<malloc.h>

#define INFINITY 100
#define MAX_VERTEX_NUM 20
#define OK 1
#define ERROR 0

typedef int Status;

typedef char VertexType;/* 顶点类型*/

typedef struct ArcNode {            //边表节点
    int adjvex;                 // 该弧所指向的顶点的位置
    int weight;                 //权值
    struct ArcNode *next;  // 指向下一条弧的指针
} ArcNode;

typedef struct VNode {         //表头节点
    char data;            // 顶点信息
    ArcNode *firstarc;   // 指向第一条依附该顶点的弧或边
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;              //表头结点表
    int vexnum, arcnum;     // 图的顶点数和弧数或边数
} ALGraph;

VertexType *array = (VertexType *) malloc(sizeof(VertexType) * MAX_VERTEX_NUM);//广搜序列存在全局数组VertexType array[]（自己定义）
int count = 0; // 用于标记已经存储了几个
int *visit = (int *) malloc(sizeof(int) * MAX_VERTEX_NUM); //定义标志数据，标记顶点是否被访问过

int LocateVex(ALGraph G, VertexType v) {
    for (int i = 0; i < G.vexnum; i++)
        if (G.vertices[i].data == v)
            return i;
    return -1;
}//返回顶点v的存储下标，不存在返回-1

Status CreateALGraph(ALGraph &G) {
    scanf("%d %d", &G.vexnum, &G.arcnum);
    getchar();
    for (int i = 0; i < G.vexnum; i++) {
        scanf("%c", &G.vertices[i].data);
        G.vertices[i].firstarc = NULL;
    }
    for (int k = 0; k < G.arcnum; k++) {
        getchar();
        int w;
        VertexType a, b;
        scanf("%c%c%d", &a, &b, &w);
        int i, j;
        i = LocateVex(G, a);
        j = LocateVex(G, b);
        ArcNode *p = (ArcNode *) malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->weight = w;
        p->next = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p;
    }
}//根据输入的顶点集合和关系集合完成邻接表的构建。

void OutDegree(ALGraph G, int OutDeg[]) {
    ArcNode *p;
    for (int i = 0; i < G.vexnum; ++i) {
        int n = 0;
        p = G.vertices[i].firstarc;
        while (p) {
            n++;
            p = p->next;
        }
        OutDeg[i]++;
    }
}//求各个顶点的出度返回在数组OutDeg。

void BFS(ALGraph G) {
    int S = 0;//从第一个顶点的下标开始
    int queue[MAX_VERTEX_NUM];
    int l = 0, r = 0;
    queue[r++]=S;
    visit[S]=1;
    ArcNode *p;
    while (l!=r){
        l++;
        array[count++]=queue[r];
        p=G.vertices[queue[r]].firstarc;
        while (p){
            if(visit[p->adjvex]!=1){
                queue[r++]=p->adjvex;
            }
            p=p->next;
        }
    }
}//对图G进行广度优先搜索